import java.io.ObjectInputStream.GetField;
import java.util.Collections;
import java.util.LinkedList;


public class Main {

	public static void main(String[] args) {
		
		Nodo hijoIzqRaiz = new Nodo(6);
		hijoIzqRaiz.setIzq(new Nodo(7));
		
		Nodo nietoDer = new Nodo(12);
		nietoDer.setIzq(new Nodo(11));
		nietoDer.setDer(new Nodo(17));
		
		Nodo hijoDerRaiz = new Nodo(9);
		hijoDerRaiz.setDer(nietoDer);
		
		Nodo raiz = new Nodo(5);
		raiz.setDer(hijoDerRaiz);
		raiz.setIzq(hijoIzqRaiz);
		
        LinkedList<Nodo> miLista;
        miLista = caminoMasLargoConNodos(raiz);

        //System.out.println("Empezoooo!!!");
        for (Nodo nodo : miLista) {
           // System.out.println(nodo);
        }

        recorrerEnOrdenNivel(raiz, 21);
        //---
	}
	
	public static void recorrerEnOrden(Nodo nodo){
		if(nodo != null){
			System.out.print(nodo+" ");
			recorrerEnOrden(nodo.getIzq());
			recorrerEnOrden(nodo.getDer());
		}
		
	}
	
	public static void recorrerPreOrden(Nodo nodo){
		if(nodo != null){
			recorrerPreOrden(nodo.getIzq());
			System.out.print(nodo+" ");
			recorrerPreOrden(nodo.getDer());
		}
		
	}
	public static void recorrerPostOrden(Nodo nodo){
		if(nodo != null){
			recorrerPostOrden(nodo.getIzq());
			recorrerPostOrden(nodo.getDer());
			System.out.print(nodo+" ");
		}
		
	}
	
	public static int sumarEnOrden(Nodo nodo){
		if(nodo != null){
			return nodo.getDato() + sumarEnOrden(nodo.getIzq()) + sumarEnOrden(nodo.getDer());
		}else
			return 0;
		
	}
	
	public static LinkedList<Nodo> caminoMasLargoConNodos(Nodo nodo){
		if(nodo != null){
            LinkedList<Nodo> der = new LinkedList<Nodo>();
            LinkedList<Nodo> izq = new LinkedList<Nodo>();
            der.add(nodo);
            der.addAll(caminoMasLargoConNodos(nodo.getDer()));

            izq.add(nodo);
            izq.addAll(caminoMasLargoConNodos(nodo.getIzq()));

            if (der.size() > izq.size()){
                return der;
            }
			return izq;
		} else {
			return new LinkedList<Nodo>();
		}		
	}

    public static void recorrerEnOrdenNivel(Nodo nodo, int a) {
		if (a == 1) {
			try {
				System.out.println("El nodo del nivel solicitado es el " + nodo.getDato());
			} catch (Exception e) {

			}
		} else {
			if (nodo != null) {
				recorrerEnOrdenNivel(nodo.getIzq(), a - 1);
				// System.out.println(nodo);
				recorrerEnOrdenNivel(nodo.getDer(), a - 1);
			}
		}

	}


    public static int caminoMasLargo(Nodo nodo){
		if(nodo != null){
			int caminoDer = 1 + caminoMasLargo(nodo.getIzq());
			int caminoIzq = 1 + caminoMasLargo(nodo.getDer());
			return ((caminoDer > caminoIzq) ? caminoDer : caminoIzq);
		} else {
			return -1;
		}
	}
	

}



/* devolver una luista con todos los nodos de la longitud mas larga.
listar todos los nodos del nivel introducido.
dado un arbol que contenga una expresion matematica  */